#include "typedef.h"

/**
 * Binary Search Tree (BST)  Implementation
 * ==========================================
 * This is the basic tree of other advance tree based data structure.
 * ================================================================================================
 * The left child of a node must be LESS than the node
 * And the right child must be  GREATER than the node's value.
 *
 * !!! Notice that euqal node is not allowed !!!
 *
 * for more basic knowledge on BST, you can refer to:
 * https://www.geeksforgeeks.org/binary-search-tree-data-structure/?ref=lbp
 *
 * DY Young @Shougang Park, Beijing, 2024 CN
 */

typedef struct BSTNode
{
    struct BSTNode *left;
    struct BSTNode *right;
    struct BSTNode *parent;
} *BSTNode;

typedef struct BSTree
{
    BSTNode root;
    boolean (*less)(BSTNode, BSTNode);
    boolean (*equal)(BSTNode, BSTNode);
    boolean (*swap)(BSTNode, BSTNode);
    void (*printer)(BSTNode);
    int nr_node;
} *BSTree;

typedef enum
{
    IN_ORDER,
    POST_ORDER,
    PRE_ORDER,
    LAYER_ORDER
} TRAVEL_STYLE;

typedef boolean (*operator)(BSTNode, BSTNode) __attribute__((__nothrow__));

static boolean bst_direct_insert_node(BSTNode root, BSTNode node, operator less)
{
    BSTNode ptr = root;
    BSTNode next = NULL;

    while (ptr)
    {
        if (less(node, ptr))
        {
            if (ptr->left)
            {
                next = ptr->left;
            }
            else
            {
                ptr->left = node;
                return True;
            }
        }
        else
        {
            if (ptr->right)
            {
                next = ptr->right;
            }
            else
            {
                ptr->right = node;
                return True;
            }
        }
        ptr = next;
    }
    return False;
}

static BSTNode bst_direct_find_node(BSTNode root, BSTNode vnode, operator less, operator equal)
{
    BSTNode ptr = root;
    while (ptr)
    {
        if (equal(vnode, ptr))
        {
            return ptr;
        }
        if (less(vnode, ptr))
        {
            ptr = ptr->left;
        }
        else
        {
            ptr = ptr->right;
        }
    }
    return NULL;
}

static BSTNode bst_direct_find_delete_node(BSTNode root, BSTNode vnode, operator less, operator equal, operator swapper)
{
    BSTNode *pa_link = NULL;
    BSTNode ptr = root;
    while (ptr)
    {
        if (less(vnode, ptr))
        {
            pa_link = &ptr->left;
            ptr = ptr->left;
        }
        else if (equal(vnode, ptr))
        {
            break;
        }
        else
        {
            pa_link = &ptr->right;
            ptr = ptr->right;
        }
    }

    // not found the node
    if (!ptr)
    {
        return NULL;
    }

    // ok, we here find the node

    if (!ptr->left && !ptr->right)
    {
        *pa_link = NULL;
        return root;
    }
    else if (!ptr->left)
    {
        if (!pa_link)
        {
            return ptr->right;
        }
        else
        {
            *pa_link = ptr->right;
        }
    }
    else if (!ptr->right)
    {
        if (!pa_link)
        {
            return ptr->left;
        }
        else
        {
            *pa_link = ptr->left;
        }
    }
    else
    {
        // the node has both left and right child
        if (!ptr->left->right)
        {
            ptr->left->right = ptr->right;
            if (!pa_link)
            {
                return ptr->left;
            }
            else
            {
                *pa_link = ptr->left;
            }
        }
        // we must find the left-tree's most right node
        BSTNode tptr = ptr;
        BSTNode *tpa_link = NULL;
        while (tptr->left || tptr->right)
        {
            if (tptr->left)
            {
                tpa_link = &tptr->left;
                tptr = tptr->left;
            }
            else
            {
                tpa_link = &tptr->right;
                tptr = tptr->right;
            }
        }
        swapper(tptr, ptr);
        *tpa_link = NULL;
    }
    return root;
}

static boolean bst_insert_node(BSTNode root, BSTNode node, operator less)
{
    BSTNode ptr = root;
    BSTNode next = NULL;

    if (less(node, root))
    {
        if (root->left == NULL)
        {
            root->left = node;
            node->parent = root;
            return True;
        }
        else
        {
            bst_insert_node(root->left, node, less);
        }
    }
    else
    {
        if (root->right == NULL)
        {
            root->right = node;
            node->parent = root;
            return True;
        }
        else
        {
            bst_insert_node(root->right, node, less);
        }
    }

    return False;
}

static BSTNode bst_find_node(BSTNode root, BSTNode vnode, operator less, operator equal)
{
    if (!root)
    {
        return NULL;
    }
    if (equal(vnode, root))
    {
        return root;
    }
    if (less(vnode, root))
    {
        return bst_find_node(root->left, vnode, less, equal);
    }
    else
    {
        return bst_find_node(root->right, vnode, less, equal);
    }
    return NULL;
}

static BSTNode bst_find_delete_node(BSTNode root, BSTNode vnode, operator less, operator equal, operator swapper)
{
    if (equal(vnode, root))
    {
        // current node only has one child
        if (root->left == NULL)
        {
            return root->right;
        }
        else if (root->right == NULL)
        {
            return root->left;
        }

        // current node has both left and right child
        // travel to the minimum leaf node of the subtree
        BSTNode p = root;
        BSTNode c = root->right;
        while (c->left != NULL)
        {
            p = c;
            c = c->left;
        }

        swapper(root, c);

        if (p->left == c)
            p->left = c->right;
        else
            p->right = c->right;
    }
    else if (less(vnode, root))
    {
        root->left = bst_find_delete_node(root->left, vnode, less, equal, swapper);
    }
    else
    {
        root->right = bst_find_delete_node(root->right, vnode, less, equal, swapper);
    }
    return root;
}

static BSTNode bst_find_minimum_node(BSTNode root)
{
    if (!root)
    {
        return NULL;
    }
    if (root->left)
    {
        BSTNode p = root;
        BSTNode c = root->left;
        while (c->left != NULL)
        {
            p = c;
            c = c->left;
        }
        return c;
    }
    return root;
}

static BSTNode bst_find_maximum_node(BSTNode root)
{
    if (!root)
    {
        return NULL;
    }
    if (root->right)
    {
        BSTNode p = root;
        BSTNode c = root->right;
        while (c->right != NULL)
        {
            p = c;
            c = c->right;
        }
        return c;
    }
    return root;
}

boolean bst_tree_init(BSTree t, operator less, operator equal, operator swap, void (*printer)(BSTNode))
{
    t->root = NULL;
    t->less = less;
    t->equal = equal;
    t->swap = swap;
    t->nr_node = 0;
    t->printer = printer;
    return True;
}

boolean bst_tree_insert(BSTree t, BSTNode node)
{
    BSTNode root = t->root;
    if (!root)
    {
        t->root = node;
        return True;
    }
    return bst_direct_insert_node(root, node, t->less);
    // return bst_insert_node(root, node, t->less);
}

boolean bst_tree_find(BSTree t, BSTNode vnode)
{
    BSTNode n = bst_find_node(t->root, vnode, t->less, t->equal);
    if (!n)
    {
        return NULL;
    }
    t->swap(n, vnode);
    return True;
}

boolean bst_tree_delete(BSTree t, BSTNode vnode)
{
    // BSTNode root = bst_find_delete_node(t->root, vnode, t->less, t->equal, t->swap);
    BSTNode root = bst_direct_find_delete_node(t->root, vnode, t->less, t->equal, t->swap);
    t->root = root;
    return True;
}

BSTNode bst_tree_find_minmum(BSTree t)
{
    return bst_find_minimum_node(t->root);
}

BSTNode bst_tree_find_maximum(BSTree t)
{
    return bst_find_maximum_node(t->root);
}

/**
 * !!! Tree visual help functions begin here !!!
 */

static void bst_print_inorder(BSTNode root, void (*printer)(BSTNode))
{
    if (!root)
        return;
    bst_print_inorder(root->left, printer);
    printer(root);
    bst_print_inorder(root->right, printer);
}

static void bst_print_postorder(BSTNode root, void (*printer)(BSTNode))
{
    if (!root)
        return;
    bst_print_postorder(root->left, printer);
    bst_print_postorder(root->right, printer);
    printer(root);
}

static void bst_print_preorder(BSTNode root, void (*printer)(BSTNode))
{
    if (!root)
        return;
    printer(root);
    bst_print_preorder(root->left, printer);
    bst_print_preorder(root->right, printer);
}

static void bst_print_layerorder(BSTNode root, void (*printer)(BSTNode))
{
#define N 20
    int cl = 0;
    int qr = 0;
    int qw = 1;
    int layer[N] = {0};
    BSTNode q[N] = {root};
    while (qr != qw)
    {
        BSTNode n = q[qr];
        if (cl != layer[qr])
        {
            printer(NULL);
            cl++;
        }
        printer(n);
        qr = (qr + 1) % N;
        if (n->left)
        {
            q[qw] = n->left;
            layer[qw] = cl + 1;
            qw = (qw + 1) % N;
        }
        if (n->right)
        {
            q[qw] = n->right;
            layer[qw] = cl + 1;
            qw = (qw + 1) % N;
        }
    }
}

void bst_tree_print(BSTree t, TRAVEL_STYLE style)
{
    switch (style)
    {
    case PRE_ORDER:
        bst_print_preorder(t->root, t->printer);
        break;
    case POST_ORDER:
        bst_print_postorder(t->root, t->printer);
        break;
    case IN_ORDER:
        bst_print_inorder(t->root, t->printer);
        break;
    default:
        bst_print_layerorder(t->root, t->printer);
        break;
    }
}

/**======= demo bst usage =======**/

#define HOST_DEBUG
#ifdef HOST_DEBUG

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TNode
{
    int value;
    struct BSTNode node;
} *TNode;

#define TNODE(n) CONTAINER_OF(TNode, node, n)

static boolean tnode_small(BSTNode l, BSTNode r)
{
    TNode ll = CONTAINER_OF(TNode, node, l);
    TNode rr = CONTAINER_OF(TNode, node, r);
    return ll->value < rr->value;
}

static boolean tnode_equal(BSTNode l, BSTNode r)
{
    TNode ll = CONTAINER_OF(TNode, node, l);
    TNode rr = CONTAINER_OF(TNode, node, r);
    printf("l %d == r %d\n", ll->value, rr->value);
    return ll->value == rr->value;
}

static boolean tnode_swap(BSTNode l, BSTNode r)
{
    TNode ll = CONTAINER_OF(TNode, node, l);
    TNode rr = CONTAINER_OF(TNode, node, r);
    printf("l %d == r %d\n", ll->value, rr->value);
    int t = ll->value;
    ll->value = rr->value;
    rr->value = t;
    return True;
}

static void tnode_print(BSTNode n)
{
    if (!n)
    {
        printf("\n");
    }
    else
    {
        TNode tn = CONTAINER_OF(TNode, node, n);
        printf("%03d ", tn->value);
    }
}

int main()
{
    BSTree tree = (BSTree)malloc(sizeof(struct BSTree));
    bst_tree_init(tree, tnode_small, tnode_equal, tnode_swap, tnode_print);

    for (int i = 0; i < 10; i++)
    {
        TNode n = (TNode)malloc(sizeof(struct TNode));
        n->value = rand() % 200;
        n->node.left = n->node.right = NULL;
        printf("add %d\n", n->value);
        bst_tree_insert(tree, &n->node);
    }

    // for(int i=20; i<30; i++)
    // {
    //     TNode n = (TNode)malloc(sizeof(struct TNode));
    //     n->value = rand() % 200;
    //     n->node.left = n->node.right = NULL;
    //     bst_tree_insert(tree, &n->node);
    // }

    bst_tree_print(tree, IN_ORDER);
    BSTNode max = bst_tree_find_maximum(tree);
    printf("max is %d\n", TNODE(max)->value);
    // TNODE(max)->value = 124;
    struct TNode ss = {169};
    bst_tree_delete(tree, &ss.node);
    printf("deleted %d\n", TNODE(&ss)->value);
    bst_tree_print(tree, IN_ORDER);
}

#endif